#define _CRT_SECURE_NO_WARNINGS

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 // void Swap(int* a, int *b)
 // {
 //     int temp = *a;
 //     *a = *b;
 //     *b = temp;
 // }

 // int Mid_Of_Three(int* nums, int num1, int num2, int num3)
 // {
 // 	if (nums[num1] > nums[num2])
 // 	{
 // 		if (nums[num3] > nums[num1])
 // 			return num1;
 // 		else if (nums[num3] > nums[num2])
 // 			return num3;
 // 		else
 // 			return num2;
 // 	}
 // 	else    //num2 > num1
 // 	{
 // 		if (nums[num3] > nums[num2])
 // 			return num2;
 // 		else if (nums[num3] > nums[num1])
 // 			return num3;
 // 		else
 // 			return num1;
 // 	}
 // }

 // void QuickSort(int* nums, int left, int right)
 // {
 //     if (left >= right)
 //         return;

 //     int mid = (right - left) / 2 + left;
 //     int mid_index = Mid_Of_Three(nums, left, right, mid);

 //     Swap(&nums[mid_index], &nums[left]);

 //     int prev = left;
 //     int cur = prev + 1;
 //     while (cur <= right)
 //     {
 //         if (nums[cur] < nums[left] && ++prev != cur)
 //             Swap(&nums[prev], &nums[cur]);

 //         cur++;
 //     }

 //     Swap(&nums[left], &nums[prev]);

 //     QuickSort(nums, left, prev - 1);
 //     QuickSort(nums, prev + 1, right);
 // }

void _MergeSort(int* nums, int* temp, int left, int right)
{
    if (left >= right)
        return;

    int mid = (right - left) / 2 + left;
    _MergeSort(nums, temp, left, mid);
    _MergeSort(nums, temp, mid + 1, right);

    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;
    int index = begin1;

    while (begin1 <= end1 && begin2 <= end2)
    {
        if (nums[begin1] < nums[begin2])
            temp[index++] = nums[begin1++];
        else
            temp[index++] = nums[begin2++];
    }

    while (begin1 <= end1)
        temp[index++] = nums[begin1++];
    while (begin2 <= end2)
        temp[index++] = nums[begin2++];

    memcpy(nums + left, temp + left, sizeof(int) * (right - left + 1));
}

void MergeSort(int* nums, int numsSize)
{
    int* temp = (int*)malloc(sizeof(int) * numsSize);

    _MergeSort(nums, temp, 0, numsSize - 1);
}

int* sortArray(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;

    // QuickSort(nums, 0, numsSize - 1);
    MergeSort(nums, numsSize);

    return nums;
}